/*
 * 
 *  h（n）表示所有数码位置与目标状态的所对应的数码位置之差的距离总和
 *  显然，h（n）<h*（n）
 * 
 * 
 * 
 * */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int endState[9] = {4,0,1,2,5,8,7,6,3};	//number -> place
int startState[9];
int *currentState;
int childState[4][9];
int tempState[9];
int step = 0;
int all = 0;

typedef struct NODE
{
	struct NODE *p;
	int id;
	int state[9];
	int setValue;	//1:open,0:undiscovery,-1:close
	int fValue;	
	struct NODE *next;
} Node;

typedef struct SET
{
	Node *open[1000000];
	Node *close;
	int tail;
} Set;

int HFunc(int currentState[])
{
	int i,a1,b1,a2,b2;
	int all = 0;
	for (i = 0;i < 9;i++)
		tempState[currentState[i]] = i;
	for(i = 1;i < 9;i++)
	{
		a1 = tempState[i]/3;
		b1 = tempState[i]%3;
		a2 = endState[i]/3;
		b2 = endState[i]%3;	
		all += abs(a1-a2) + abs(b1-b2);
	}
	return all;
}

void MoveNode(Set *set,int from,int to)
{	
	Node *node;
	int t;
	node = set->open[from];
	set->open[from] = set->open[to];
	set->open[to] = node;	
	t = set->open[from]->id;	
	set->open[from]->id = set->open[to]->id;
	set->open[to]->id = t;	
}

void InsertClose(Set *set,int id)
{	
	if(set->tail != id)
		MoveNode(set,set->tail,id);
	if(set->close != NULL)
	{
		Node *temp =set->close;
		set->close = set->open[set->tail];
		set->open[set->tail]->next = temp;
	}
	else
		set->close = set->open[set->tail];				
	set->open[set->tail]->setValue = -1;
	set->tail--; 
	int t= id;	
	while( t * 2 <= set->tail)
	{
		if( set->tail == 2 * t)
		{
			MoveNode(set,t,set->tail);
			t = set->tail;
		}
		else if(set->open[2*t]->fValue < set->open[2*t+1]->fValue )
		{	
			MoveNode(set,t,2*t);
			t = 2 * t;			
		}
		else
		{	
			MoveNode(set,t,2*t+1);
			t = 2 * t + 1;			
		}
	}
}

void InsertOpen(Set *set,Node *node)
{
	if(set->tail < 0)
	{
		set->open[0] = node;
		set->tail = 0;
		set->open[0]->id = 0;
		return;
	}
	set->tail ++;
	node->id = set->tail;
	int t = node->id;
	set->open[set->tail] = node;
	while(t > 0 && set->open[t]->fValue < set->open[t/2]->fValue)
	{
			MoveNode(set,t,t/2);
			t = t/2;
	}	
}

Node *Success(Set *set,Node *node)
{
	Node *start,*temp;
	start = node;
	start->next = NULL;
	all++;
	while(node->p!=NULL)
	{
		temp = start;
		start = node->p;
		start->next = temp;
		node = node->p;
		all++;
	}
	return start;
}

Node *InitNode(int *state)
{
	Node *node = malloc(sizeof(Node));
	int i;
	for(i = 0;i < 9;i++)
		node->state[i] = state[i];
	node->next=NULL;
	node->p=NULL;
	node->id = -1;
	node->setValue = 0;
	node->fValue = HFunc(state) + step;
	return node;
}

Node *Search(Set *set,int *state)
{
	Node *temp = set->close;
	int i,k,discover = 1;
	for(i = 0;i < 9;i++)
		if(temp->state[i]!=state[i])
		{
			discover = -1;
			break;
		}
	if(discover == 1)
		return temp;
	while(temp->next!=NULL)
	{	
		discover = 1;
		for(i = 0;i < 9;i++)
		{
			if(temp->next->state[i]!=state[i])
			{
				discover = -1;
				break;
			}
		}
		if(discover == 1)
			return temp->next;
		temp = temp->next;
	}
	
	for(k = 0;k < set->tail;k++)
	{
		discover = 1;
		for(i = 0;i < 9;i++)
			if(temp->state[i]!=state[i])
			{
				discover = -1;
				break;
			}
		if(discover == 1)
			return temp;
	}
	Node *node = InitNode(state);
	return node;
}

void Update(Set *set,Node *current,int childState[][9])
{
	int i;
	Node *node;
	for(i = 0;i < 4;i++)
	{
		int *state = childState[i];
		if(state[0] != -1)
		{
			node = Search(set,state);		
			if(node->setValue == 0)	//the state is undiscovered
			{
				node->p = current;
				node->setValue = 1;	//set open								
				InsertOpen(set,node);						
			}

		}
	}
}

void CreateChild(int currentState[])
{
	int i,j,t,temp,a,b,p;
	for(i = 0;i < 4;i++)
		for(j = 0;j < 9;j++)
			childState[i][j]=currentState[j];
	for(i = 0;i < 9;i++)
		if(currentState[i] == 0)
		{	
			t = i;
			break;
		}
	a = t / 3;
	b = t % 3;
	if(a > 0)
	{
		p = (a - 1)*3 + b;
		temp = childState[0][p];
		childState[0][p] = 0;	//set 0 at (a-1,b)
		childState[0][t] = temp;	//move number at(a-1,b) to (a,b)	
	}
	else
		childState[0][0] = -1;	//if number 0 at (0,*) then set not exist
	if(b > 0)
	{
		p = a*3 + b - 1;
		temp = childState[1][p];		
		childState[1][p] = 0;	//set 0 at (a,b-1)
		childState[1][t] = temp;	//move number at(a,b-1) to (a,b)			
	}
	else
		childState[1][0] = -1;	//if number 0 at (*,0) then set not exist
	if(a < 2)
	{
		p = (a + 1)*3 + b;
		temp = childState[2][p];
		childState[2][p] = 0;	//set 0 at (a+1,b)
		childState[2][t] = temp;	//move number at(a+1,b) to (a,b)	
	}
	else
		childState[2][0] = -1;	//if number 0 at (2,*) then set not exist
	if(b < 2)
	{
		p = a*3 + b + 1;
		temp = childState[3][p];		
		childState[3][p] = 0;	//set 0 at (a,b+1)
		childState[3][t] = temp;	//move number at(a,b+1) to (a,b)			
	}
	else
		childState[3][0] = -1;	//if number 0 at (*,2) then set not exist
}

void Print(FILE *fp,Node *node)
{
	fprintf(fp,"%d %d %d\n",node->state[0],node->state[1],node->state[2]);
	fprintf(fp,"%d %d %d\n",node->state[3],node->state[4],node->state[5]);
	fprintf(fp,"%d %d %d\n",node->state[6],node->state[7],node->state[8]);
	fprintf(fp,"\n");
}

int main(int argc,char *argv[])
{
	FILE *fp,*ft;
	int success = 0;
	fp=fopen(argv[1],"r");
	ft=fopen(argv[2],"w");
	fscanf(fp,"%d %d %d",&startState[0],&startState[1],&startState[2]);
	fscanf(fp,"%d %d %d",&startState[3],&startState[4],&startState[5]);
	fscanf(fp,"%d %d %d",&startState[6],&startState[7],&startState[8]);
	int i,j,sum = 0;
	for(i = 0;i < 9;i++)
		for(j = 0;j < i;j++)
			if(startState[j] != 0 && startState[j] < startState[i])
				sum ++;
	if(sum % 2 == 0)
	{
		fprintf(ft,"no solution\n");
		return 0;
	}
	Node *start = InitNode(startState);	
	Node *temp,*node;
	start->setValue = 1;
	start->id = 0;
	Set *set = malloc(sizeof(Set));
	set->open[0] = start;
	set->tail = 0;
	while(set->tail >= 0)
	{
		node = set->open[0];
		currentState = node->state;	
		step++;
		if(HFunc(currentState) == 0)
		{
			success = 1;
			break;
		}
		CreateChild(currentState);
		InsertClose(set,0);
		Update(set,node,childState);		
	}
	if(success)
	{
		temp = Success(set,node);
		fprintf(ft,"%d\n\n",all-1);	
		while(temp->next!=NULL)
		{
			Print(ft,temp->next);
			temp = temp->next;
		}
	}
	else
		fprintf(ft,"no solution\n");
	return 0;
}
